package leetcode_jz_offer.day15_huisuAndBintree;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
 * 要求不能创建任何新的节点，只能调整树中节点指针的指向。
 **/
public class Num36_二叉搜索树与双向链表 {
    private class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };
    Node pre;//前驱结点
    Node head;//头节点
    public Node treeToDoublyList(Node root) {
        if(root==null){
            return null;
        }
        //此时节点不为空，让二叉树转为双向列表
        dfs(root);
        //此时得到了链表是双向链表，头节点是head,尾结点是prev（cur走到空时pre刚好走到尾部）
        //头节点.pre是尾结点，尾结点.next是头节点即得到循环链表
        head.left=pre;
        pre.right=head;
        return head;
    }
    //二叉树转为双向链表——通过中序遍历（中序遍历结果是一个排序好的顺序值）
    private void dfs(Node cur) {
        //1.当前结点cur为空，已越过叶子节点,直接返回
        if(cur==null){
            return;
        }
        //2.遍历左子树
        dfs(cur.left);
        //3.处理节点
        //判断前驱pre是否为null，为null说明cur是头节点
        if(pre==null){
            head=cur;
        }else{
           pre.right=cur;
        }
        cur.left=pre;
        //更新pre的值为cur：即节点cur是后继节点的pre
        pre=cur;
        /**
         * if(prev!=null){
         *                         //prev的下一位是待处理的根节点，但不是头节点
         *                         //连接
         *                         prev.right=root;
         *                         root.left=prev;
         *                         //prev往后走一位
         *                         prev=root;
         *                 }else{
         *                         //prev的下一位即root就是头节点
         *                         head=root;
         *                         prev=head;
         *                 }
         */
        //4.遍历右子树
        dfs(cur.right);
    }
}
